|
The jeep problem, desert crossing problem or exploration problem〔"Exploration problems. Another common question is concerned with the maximum distance into a desert which could be reached from a frontier settlement by an explorer capable of carrying provisions that would last him for ''a'' days." W. W. Rouse Ball and H.S.M. Coxeter (1987). ''Mathematical Recreations and Essays'', Thirteenth Edition, Dover, p32. ISBN 0-486-25357-0.〕 is a mathematics problem in which a jeep must maximise the distance it can travel into a desert with a given quantity of fuel. The jeep can only carry a fixed and limited amount of fuel, but it can leave fuel and collect fuel at fuel dumps anywhere in the desert. The problem was solved by N. J. Fine in 1947.〔 ==Problem== There are ''n'' units of fuel stored at a fixed base. The jeep can carry at most 1 unit of fuel at any time, and can travel 1 unit of distance on 1 unit of fuel (the jeep's fuel consumption is assumed to be constant). At any point in a trip the jeep may leave any amount of fuel that it is carrying at a fuel dump, or may collect any amount of fuel that was left at a fuel dump on a previous trip, as long as its fuel load never exceeds 1 unit. There are two variants of the problem: *Exploring the desert the jeep must return to the base at the end of every trip. *Crossing the desert the jeep must return to the base at the end of every trip except for the final trip, when the jeep travels as far as it can before running out of fuel. In either case the objective is to maximise the distance travelled by the jeep on its final trip. Alternatively, the objective may be to find the least amount of fuel required to produce a final trip of a given distance. In the classic problem the fuel in the jeep and at fuel dumps is treated as a continuous quantity. More complex variations on the problem have been proposed in which the fuel can only be left or collected in discrete amounts.〔(Optimal Logistics for Expeditions: the Jeep Problem with Complete Refilling ), Gunter Rote and Guochuan Zhang, June 1996〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Jeep problem」の詳細全文を読む スポンサード リンク
|